[Lecture 4:2/3] Using Randomness in Computer Science

2011-01-31 48

Lecture @ MPRI Paris Master of Computer Science (Université Paris Diderot) by Nicolas Schabanel
Jan 12, 2011 - 16:15-19:15 - Guessing by sampling
• A lot of certificates puts Zero-P in BPP
• The presence of a lot of certificates allows linearity testing
• Random self-reduction allows linearity self-correcting

Free Traffic Exchange